We are given a secure PRG $G(seed:str[S])\to str[R]$ and need to prove that it is unpredictable. Suppose, towards contradiction, that $G$ is predictable, i.e. there exists is an index $i$ and an efficient algorithm $\mathcal{A}$ which when given the bits $y[0],y[1],...,y[i]$ of the output of $\text{G}$ can guess the bit $y[i+1]$ with probability $\alpha \ge \frac{1}{2}+\xi (R)$ for some non-negligible $\xi$ (yes, even if the algorithm works for a single position in the output, then the PRG is predictable). We define the following statistical test (or distinguisher)

$$D(y)=\{\begin{array}{l}1,\text{ if }\mathcal{A}(y[0],y[1],...y[i])=y[i+1]\\ 0,\text{ otherwise}\end{array}$$

Essentially, $D$ outputs 1 if the algorithm $\mathcal{A}$ guesses correctly. If the string $y$ is chosen from a uniform distribution, i.e. $y{\leftarrow }_R\{0,1{\}}^R$, then the algorithm $\mathcal{A}$ has no information and cannot guess the bit $y[i]$ with any probability better than $\frac{1}{2}$. On the other hand, if $y$ is generated by $G$, then the algorithm $\mathcal{A}$ can guess $y[i]$ with probability $\alpha \ge \frac{1}{2}+\xi (R)$ which means that there is a statistical test which can differentiate between a string generated by $G$ and a truly uniformly chosen string which contradicts the original assumption that $G$ is secure.

For the other direction, we are given a generator $G(seed:str[S])\to str[R]$ that is unpredictable for all positions $i\in \{0,1,...,R-1\}$. We want to prove that $G$ is secure. We will denote by $G_i{U}_{R-i}$ a string of which the first $i$ bits were generated using $G$ and the rest $R-i$ bits were chosen according to a uniform distribution. We denote the distribution of such strings as $H_i$. It is clear that $H_0$ is the uniform distribution $U_R$ and $H_R$ is $\{G(s){\}}_{s{\leftarrow }_R\mathcal{S}}$. We need to show that $H_{i-1}\approx H_i$ for all $i$.

Suppose, towards contradiction, that $H_{i-1}\not\approx H_i$ for some $i$,, i.e. there is a distinguisher $D$ such that

$$\left|\underset{x\sim H_{i-1}}{\mathrm{Pr}}[D(x)=1]-\underset{x\sim H_i}{\mathrm{Pr}}[D(x)=1]\right|>\xi (R)$$

for some non-negligible $\xi (R)$.

TODO

We are given the algorithm $\text{GenT}(seed:str[S])\to str[T]$ with seed space $\mathcal{S}=\{0,1{\}}^S$ and we need to prove that it is secure.

Let's introduce some notation. We denote by $U_i{\text{Gen}}_{T-i}$ a string whose first $i$ bits were chosen according to the uniform distribution over $\{0,1{\}}^{i+1}$ and whose remaining $T-i$ bits were generated by the same algorithm that $\text{GenT}$ uses with some seed $s_i{\leftarrow }_R\mathcal{S}$. We denote by $H_i$ the distribution of strings generated in this way. Therefore, $H_0$ is the distribution obtained by sampling the seed space and outputting only $\text{GenT}$, for there are no bits chosen from a uniform distribution in this case. Conversely, $H_T$ denotes the uniform distribution over $\{0,1{\}}^T$ because no bits are generated by the same algorithm that $\text{GenT}$ uses.

We need to show that $H_0\approx H_T$ which can be done by using the Randomness and just showing that $H_i\approx H_{i+1}$ for all $i\in \{0,1,...,T-1\}$.

Suppose, towards contradiction, that there is a statistical test $D(y:str[T])\to \text{bit}$ and some $i$ such that

$$\left|\underset{y\sim H_i}{\mathbb{E}}[D(y)=1]-\underset{y\sim H_{i+1}}{\mathbb{E}}[D(y)=1]\right|\ge ϵ$$

for some non-negligible $ϵ$.

We now construct an algorithm $D^{\prime }(y:str[S+1])\to bit$ which will interpret the $y$ as an output of $\text{Gen}(s_i)$ at some stage which used a seed which we will call $s_i$. This output is comprised of a seed for the next stage, i.e. $s_{i+1}:=y[0]y[1]\cdots y[S-1]$, and one output bit, $y[S]$. Subsequently, $D^{\prime }$ generates a string $z$ of length $T$. The bits $z[0],z[1],...,z[S-1]$ are chosen according to a uniform distribution, the algorithm then copies the bit $y[S]$ into $z[S]$ and finally it generates the bits $z[S+1],z[S+2],...,z[T-1]$ by using the same process as $\text{GenT}$ does, utilising $s_{i+1}$ as the initial seed. At the end, $D^{\prime }$ will simply return $D(z)$.

#![allow(unused)]
fn main() {
fn D'(y: str[S+1]) -> bit {
	let z: str[T];
	
	for (let j = 0; j < S; ++j) { // i is the constant for which we assume that H_i is distinguishable from H_(i+1)
		z[j] = random_bit(); // Initialise the first i bits, i.e. z[0],...,z[i-1] to uniformly random values
	}
	z[S] = y[S]; // copy the i-th bit from y
	
	let current_seed = y[0..S]; // Interpret the first i bits of y as the initial seed
	
	for (let j = S + 1; j < T; ++) { // Execute the same algorithm as GenT to generate the remaining bits of z
		let pseudorandom_str = Gen(current_seed);
		z[j] = pseudorandom_str[S];
		current_seed = pseudorandom_str[0..S]
	}
	return D(z); // Return whatever value D will give for the string z;
}
}

If $D$ is efficient, then $D^{\prime }$ is also clearly efficient, so we need not worry about this anymore. Now, if $y$ is chosen according to a uniform distribution, then $D^{\prime }$ will feed into $D$ the string $z$ which would be distributed according to $H_{i+1}$ with $i=S$, since the bits $z[0],z[1],...,z[i-1]$ are generated according to a random distribution, the bit $z[i]$ is copied from $y[i]$, which was in itself chosen according to a random distribution, and the rest of the bits are generated also generated by $\text{Gen}$. On the other hand, if $y=\text{Gen}(s)$ was the output of $\text{Gen}$ for some seed $s$, then $D^{\prime }$ will feed into $D$ the string $z$ which would distributed according to $H_i$, since the bits $z[0],z[1],...,z[i-1]$ are generated according to a random distribution, $z[i]$ is copied from $y[i]$, which was generated by $\text{Gen}$, and the rest of the bits are generated by $\text{Gen}$. Under our assumption it follows that

$$\left|\underset{x{\leftarrow }_R\{0,1{\}}^S}{\mathbb{E}}[D^{\prime }(z:=\text{Gen}(x))=1]-\underset{z{\leftarrow }_R\{0,1{\}}^T}{\mathbb{E}}[D^{\prime }(z)=1]\right|\ge ϵ$$

But this contradicts the security of $\text{Gen}$.